import java.util.ArrayList;
import java.util.List;

public class Test14 {
    //定义全局变量 ret 用来收集结果
    int N = 4;
    int[] nums = {0, 1, 2, 3};
    List<List<Integer>> ret;//用集合来表示二维数组
    List<Integer> path;//用来保存每一次结果
    boolean[] check;//用来表示某个元素是不是已经被选取过
    List<Integer> minPath;//用来保存最短的路径进过的城市
    int minValue = Integer.MAX_VALUE;//用来保存最短路程
    int[][] graph = new int[N][N];//用来存储图的路径

    //为图初始化
    public void addEdge(int v1, int v2, int weight) {
        graph[v1][v2] = graph[v2][v1] = weight;
    }


    public void initGraph() {
        addEdge(0, 1, 30);
        addEdge(0, 2, 6);
        addEdge(0, 3, 4);
        addEdge(1, 3, 21);
        addEdge(2, 3, 11);
    }

    public List<List<Integer>> permute(int[] nums) {
        //1.初始化
        ret = new ArrayList<>();
        path = new ArrayList<>();
        path.add(0);
        check = new boolean[nums.length];
        minPath = new ArrayList<>();
        //2.调用dfs(回溯的核心)
        dfs(0, nums);
        return ret;
    }

    //判断路径是否合法
    public boolean legal(int index, int n) {
        int v1 = path.get(n);//得到当前城市的前一个城市的数组下标
        int v2 = index;//当前城市的数组下标
        return graph[v1][v2] != 0 && check[index] == false;
    }

    //判断最后一个城市到达0号城市是否有路径
    public boolean legalLast() {
        int v1 = path.get(0);
        int v2 = path.get(path.size() - 1);
        return graph[v1][v2] != 0;
    }

    public void dfs(int n, int[] nums) {
        //证明到达了0号城市之前的最后一个城市
        if (n == nums.length - 1) {
            //判断最后一个城市到达0号城市是否有路径
            if (legalLast()) {
                List<Integer> tmp = new ArrayList<>();
                for (int i = 0; i < path.size(); i++) {
                    tmp.add(path.get(i));
                }
                path.add(0);
                tmp.add(path.get(path.size() - 1));
                ret.add(new ArrayList<>(tmp));
                int tmpRoad = 0;
                // tmpRoad 计算本次路程的总和，然后和minValue进行比较
                for (int i = 1; i < path.size(); i++) {
                    int v1 = path.get(i - 1);
                    int v2 = path.get(i);
                    tmpRoad += graph[v1][v2];
                }
                //保留上次的最短路径
                int minTmp = minValue;
                minValue = Math.min(minValue, tmpRoad);
                //如果最短路程和有改变，就将最短路程保留到minPath中
                if (minValue != minTmp) {
                    for (int i = 0; i < path.size(); i++) {
                        minPath.add(path.get(i));
                    }
                }
            }

        }else{
            //开始匹配
            //从1号城市开始
            for (int i = 1; i < nums.length; i++) {
                if (legal(i, n)) {
                    check[i] = true;
                    path.add(i);
                    dfs(n + 1, nums);
                    //恢复现场
                    check[i] = false;
                    path.remove(n);
                }
            }
        }
    }

    public static void main(String[] args) {
        Test14 test14 = new Test14();
        test14.initGraph();
        test14.permute(test14.nums);
        System.out.println(test14.minValue);
        for (int i = 0; i < test14.minPath.size(); i++) {
            System.out.print(test14.minPath.get(i) + " ");
        }
    }


}

//    static int N = 4;//城市的个数
//    static int[][] graph = new int[N][N];
//    static int[] check = new int[N + 1];
//    static int dist;
//
//    //为图初始化
//    public static void addEdge(int v1, int v2, int weight) {
//        graph[v1][v2] = graph[v2][v1] = weight;
//    }
//
//    public static void initGraph() {
//        addEdge(0, 1, 30);
//        addEdge(0, 2, 6);
//        addEdge(0, 3, 4);
//        addEdge(1, 3, 21);
//        addEdge(2, 3, 11);
//    }
//
//    //进行合法判断
//    public static boolean legal(int t) {
//        int v1 = check[t - 1];//上一个城市
//        int v2 = check[t];
//        return graph[v1][v2] != 0;
//    }
//
//    //交换
//    public static void swap(int[] tmp, int i, int j) {
//        int t = tmp[i];
//        tmp[i] = tmp[j];
//        tmp[j] = t;
//    }
//
//    //回溯
//    //t：层数；x：累加的路程
//    public static void backTrack(int t) {
//        if (t == N) {
//            output();
//        } else {
//            for (int i = t; i < N; i++) {
//                swap(check, i, t);
//                if (legal(t)) {
//                    backTrack(t + 1);
//                }
//                swap(check, i, t);
//            }
//        }
//    }
//
//    //output
//    public static void output() {
//        int dist = 0;
//        for (int i = 1; i < N + 1; i++) {
//            int v1 = check[i - 1];
//            int v2 = check[i];
//            dist += graph[v1][v2];
//            System.out.print(check[i] + " ");
//        }
//        System.out.println(dist);
//    }
//
//    public static void main(String[] args) {
//        initGraph();
//        backTrack(0);
//    }